import copy

n = 4
board = [[0 for _ in range(n)] for _ in range(n)]


def isValid():
    for i in range(n):
        for j in range(i, n):
            if board[i][j] != board[j][i]:
                return False
    for i in range(n):
        c = 0
        for j in range(n):
            if board[i][j]:
                c += 1
                if c == 2:
                    return False
    for j in range(n):
        c = 0
        for i in range(n):
            if board[i][j]:
                c += 1
                if c == 2:
                    return False
    return True


ans = list()


def dfs(index, cnt):
    global ans
    if index == n * n:
        if cnt == n and isValid():
            ans.append(copy.deepcopy(board))
        return
    x = index // n
    y = index % n
    board[x][y] = 1
    dfs(index + 1, cnt + 1)
    board[x][y] = 0
    dfs(index + 1, cnt)


dfs(0, 0)
print(ans)
